package cn.willbj.brief.hootl.sort.demo;

import java.util.Arrays;

public class Demo02 {
	
	public static void main(String[] args) {
		int[] arr = {7,8,1,9,4};
		int[] copyOf = qSort(arr);
		System.out.println(Arrays.toString(copyOf));
	}
	
	public static int[] qSort(int[] arr) {
		int[] copyOf = Arrays.copyOf(arr, arr.length);
		qSortBiz(copyOf, 0, copyOf.length-1);
		return copyOf;
	}
	
	public static void qSortBiz(int[] arr,int left,int right) {
		if (left >= right) {
			return;
		}
		// 找基准
		int partition = partition(arr, left, right);
		
		// 左右子分区递归
		qSortBiz(arr, left, partition-1);
		qSortBiz(arr, partition + 1, right);
		
	}
	
	public static int partition(int[] arr,int left,int right) {
		int partition = left;
		int index = partition +1; // 待和基准置换的位置点
		
		for (int i = index; i <= right; i++) {
			if (arr[i] < arr[partition]) {
				swap(arr, index, i);// 置换
				index++;// 指向下一个位置
			}
		}
		swap(arr, index-1, partition);
		return index-1;
		
	}
	
	public static void swap(int[] arr,int index,int i) {
		if (index == i) {
			return;
		}
		int temp = arr[index];
		arr[index] = arr[i];
		arr[i] = temp;
	}
	
	

}
